/*
 * regex.cpp
 *
 *  Created on: 2009-10-10
 *      Author: fanliangliang
 */

#include "regex.h"
#include <string>
#include <iostream>

using namespace std;

static int match(const char* regex, const char* text);
static int matchhere(const char* regex, const char* text);
static int matchstar(int c, const char* regex, const char* text);
static int matchqo(int c, const char* regex, const char* text);
static int matchplus(int c, const char* regex, const char* text);

/* match: search for regex anywhere in text */
int match(const char* regex, const char* text) {
	if (regex[0] == '^')
		return matchhere(regex + 1, text);
	do { /* must look even if string is empty */
		if (matchhere(regex, text))
			return 1;
	} while (*text++ != '\0');
	return 0;
}

/* matchhere: search for regex at beginning of text */
int matchhere(const char* regex, const char* text) {
	if (regex[0] == '\0')
		return 1;
	if (regex[1] == '?')
		return matchqo(regex[0], regex + 2, text);
	if (regex[1] == '+')
		return matchplus(regex[0], regex + 2, text);
	if (regex[1] == '*')
		return matchstar(regex[0], regex + 2, text);

	if (regex[0] == '$' && regex[1] == '\0')
		return *text == '\0';
	if (*text != '\0' && (regex[0] == '.' || regex[0] == *text))
		return matchhere(regex + 1, text + 1);
	return 0;
}

/* matchstar: search for c*regex at beginning of text */
int matchstar(int c, const char* regex, const char* text) {
	do { /* a * matches zero or more instances */
		if (matchhere(regex, text))
			return 1;
	} while (*text != '\0' && (*text++ == c || c == '.'));
	return 0;
}

/* matchqo: search for c?regex at beginning of text */
int matchqo(int c, const char* regex, const char* text) {
	int i = 0;
	do { /* a * matches zero or more instances */
		if (matchhere(regex, text))
			return 1;
		++i;
	} while (i < 2 && *text != '\0' && (*text++ == c || c == '.'));
	return 0;
}

/* matchplus: search for c+regex at beginning of text */
int matchplus(int c, const char* regex, const char* text) {
	while (*text != '\0' && (*text++ == c || c == '.')) {
		if (matchhere(regex, text))
			return 1;
	}
	return 0;
}


bool regex_match(const char* regex, const char* text) {
	if (regex == 0 || text == 0) {
		return false;
	}
	return match(regex, text);
}

bool wildcard_match(const char* pattern, const char* text) {
	if (pattern == 0 || text == 0) {
		return false;
	}

	char a = pattern[0];
	char b = text[0];
	if (a == '\0') {
		return b == '\0';
	}
	if (a == '*') {
		return wildcard_match(pattern + 1, text) || b != '\0' && wildcard_match(pattern, text + 1);
	}
	if (a == '?') {
		return b != '\0' && wildcard_match(pattern + 1, text + 1);
	}

	return (a == b) && wildcard_match(pattern + 1, text + 1);
}
